|
数学のグラフ理論の分野における内周(ないしゅう、)とは、グラフに含まれる最小の閉路の長さのことを言う〔R. Diestel, ''Graph Theory'', p.8. 3rd Edition, Springer-Verlag, 2005〕。もしもグラフが閉路を含まないなら(すなわち、無閉路グラフであるなら)、その内周は無限大と定義される。例えば、(平方)4-閉路グラフの内周は4である。格子グラフの内周も4である。三角形メッシュの内周は3である。内周が4以上のグラフは、である。 == ケージ == 立方体グラフ(すべての頂点の次数が3であるグラフ)で、その内周が(可能な限り最小な) ''g'' であるようなものは、''g''-(あるいは (3,''g'')-ケージ)として知られる。ピーターセングラフは唯一つの 5-ケージであり(内周が5であるような最小の立方体グラフである)、ヒーウッドグラフは唯一つの 6-ケージ、は唯一つの 7-ケージ、は唯一つの 8-ケージである〔. Electronic supplement to the book ''Distance-Regular Graphs'' (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).〕。与えられた内周に対して、複数のケージが存在することもある。例えば、70個の頂点を持つ非同型な10-ケージは、三つ存在する:と、およびである。 Image:Petersen1 tiny.svg|ピーターセングラフの内周は5である。 Image:Heawood_Graph.svg|ヒーウッドグラフの内周は6である。 Image:McGee graph.svg|の内周は7である。 Image:Tutte eight cage.svg|(''トゥッテ8-ケージ'')の内周は8である。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「内周 (グラフ理論)」の詳細全文を読む スポンサード リンク
|